package problem72_Edit_Distance;
/**
 * 
 * 
 * @see <a href="http://www.cnblogs.com/AndyJee/p/4602817.html" />
 * @see <a href="http://blog.csdn.net/monkeyduck/article/details/51469357" />
 * @author Ivan
 *
 */

public class Solution {
	public int minDistance(String word1, String word2) {
		int m=word1.length(),n=word2.length();
		int[][] minDistance=new int[m+1][n+1];
		for(int i=1;i<=m;i++) minDistance[i][0]=i;
		for(int j=0;j<=n;j++) minDistance[0][j]=j;
		for(int i=1;i<=m;i++){
			for(int j=1;j<=n;j++){
				if(word1.charAt(i-1)==word2.charAt(j-1)){
					minDistance[i][j]=minDistance[i-1][j-1];
				}else{
					minDistance[i][j]=Math.min(Math.min(minDistance[i-1][j-1], minDistance[i-1][j]),minDistance[i][j-1])+1;
				}
			}
		}
		return minDistance[m][n];
    }
}
